//
//  _BinarySearchTree.hpp
//  KV_BinarySearchTree
//
//  Created by 卜绎皓 on 2022/11/7.
//

#pragma once
#include<iostream>
#include<string>
using namespace std;

namespace KEY
{
    //...
}
namespace KEY_VALUE
{
    template<class K, class V>
    struct BSTreeNode
    {
        BSTreeNode<K, V>* _left;
        BSTreeNode<K, V>* _right;
        K _key;
        V _value;

        BSTreeNode(const K& key, const V& value)
            : _left(nullptr)
            , _right(nullptr)
            , _key(key)
            , _value(value)
        {}
    };
    template<class K, class V>
    class BSTree
    {
        typedef BSTreeNode<K, V> Node;
    public:
        bool Insert(const K& key, const V& value)
        {
            //空树,直接插入
            if (_root == nullptr)
            {
                _root = new Node(key, value);
                return true;
            }
            //查找要插入的位置
            Node* parent = nullptr;
            Node* cur = _root;
            while (cur)
            {
                if (cur->_key < key)//往右子树查找
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)//往左子树查找
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return false;//默认不支持冗余
                }
            }
            //new节点,这里需要在BSTreeNode补构造函数
            cur = new Node(key, value);
            if (parent->_key < cur->_key)//新节点链接到父的左还是右,还需要再比一次
            {
                parent->_right = cur;//关联
            }
            else
            {
                parent->_left = cur;//关联
            }
            return true;
        }
        Node* Find(const K& key)
        {
            Node* cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    cur = cur->_left;
                }
                else
                {
                    return cur;
                }
            }
            return nullptr;
        }
        bool Erase(const K& key)
        {
            Node* parent = nullptr;
            Node* cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    //删除
                    if (cur->_left == nullptr)//ab
                    {
                        //没有父亲
                        if (cur == _root)
                        {
                            _root = cur->_right;//右作根
                        }
                        else
                        {
                            //确定目标位置父亲的左还是右和目标位置的孩子关联(目标位置的左右孩子在外层if已经确定了)
                            if (cur == parent->_left)
                            {
                                parent->_left = cur->_right;
                            }
                            else
                            {
                                parent->_right = cur->_right;
                            }
                        }
                        delete cur;
                    }
                    else if (cur->_right == nullptr)//ac
                    {
                        //没有父亲
                        if (cur == _root)
                        {
                            _root = cur->_left;
                        }
                        else
                        {
                            //确定目标位置父亲的左还是右和目标位置的孩子关联(目标位置的左右孩子在外层if已经确定了)
                            if (cur == parent->_left)
                            {
                                parent->_left = cur->_left;
                            }
                            else
                            {
                                parent->_right = cur->_left;
                            }
                        }
                        delete cur;
                    }
                    else//d
                    {
                        //找右树的最小节点去替代删除
                        Node* minRightParent = cur;
                        //cur->right一定不为空
                        Node* minRight = cur->_right;
                        //最小节点
                        while (minRight->_left)
                        {
                            minRightParent = minRight;
                            minRight = minRight->_left;
                        }
                        //替代
                        cur->_key = minRight->_key;
                        //minRight的左一定为空,但右不一定为空,minRightParent->_left不一定是minRight
                        if (minRight == minRightParent->_left)//删除5,找6
                        {
                            minRightParent->_left = minRight->_right;
                        }
                        else//删除7,找8
                        {
                            minRightParent->_right = minRight->_right;
                        }
                        delete minRight;
                    }
                    return true;
                }
            }
            return false;
        }
        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }
    private:
        void _InOrder(Node* root)
        {
            if (root == nullptr)
            {
                return;
            }
            _InOrder(root->_left);
            cout << root->_key << ":" << root->_value << endl;
            _InOrder(root->_right);
        }
    private:
        Node* _root = nullptr;
    };
}
